﻿package astar {

	/**
	 * ...
	 * @author test
	 */
	public class MinHeap {
		public var data:Array;
		public var compare:Function;
		public var size:uint;

		static public var SMALLER:int = -1;
		static public var BIGGER:int = 1;
		static public var EQUAL:int = 0;
		static public var ROOT:uint = 1;

		public function MinHeap(_compare:Function){
			data = new Array();
			size = new uint(0);

			compare = _compare;
		/*
		   for (var i:uint = 0; i < 16; i++)
		   push(Math.floor(Math.random() * 100));
		   print();
		   var t:String = new String();
		   for (var i:uint = 0; i < data.length - 1; i++){
		   //if (i == data.length - 3)
		   //print();

		   t += pop() + ", ";

		   }
		   trace(t);
		 */
		}

		public function swap(a:uint, b:uint, arr:Array):void {
			var tmp:* = arr[a];
			arr[a] = arr[b];
			arr[b] = tmp;
		}

		public function push(_x:*):* {
			size++;

			var cur_loc:uint = size;
			var par_loc:uint = cur_loc >> 1;

			data[cur_loc] = _x;

			while (cur_loc != ROOT && compare(data[cur_loc], data[par_loc]) == SMALLER){
				swap(cur_loc, par_loc, data);

				cur_loc = par_loc;
				par_loc = cur_loc >> 1;
			}

			return _x;
		}

		public function pop():* {
			if (size == 0){
				throw("ERROR");
			}

			var root_dat:* = data[1];
			var curNode:uint = 1;
			var child:uint = 2;
			var lastE:* = data[size--];
			while (child <= size){
				if (child < size && compare(data[child], data[child + 1]) == BIGGER){
					child++;
				}
				if (compare(lastE, data[child]) == SMALLER){
					break;
				}

				data[curNode] = data[child];
				curNode = child;
				child <<= 1;
			}
			data[curNode] = lastE;
			/*
			   data[1] = data[size];

			   size--;

			   if (size > 0){
			   var cur_loc:uint = 1;
			   var l_child:uint = cur_loc << 1;
			   var r_child:uint = l_child + 1;

			   while (cur_loc <= size && l_child <= size && r_child <= size && (compare(data[cur_loc], data[l_child]) == BIGGER || compare(data[cur_loc], data[r_child]) == BIGGER)){
			   //trace(cur_loc, data[cur_loc]);
			   var smaller_loc:uint = compare(data[l_child], data[r_child]) == SMALLER ? l_child : r_child;
			   swap(cur_loc, smaller_loc, data);

			   cur_loc = smaller_loc;
			   l_child = cur_loc << 1;
			   r_child = l_child + 1;
			   }
			   }
			 */
			return root_dat;
		}

		public function print():void {
			var output:String = new String();
			var bin_count:uint = 2;
			for (var i:Number = 1; i <= size; i++){
				output += data[i] + ", ";
				if (i == bin_count - 1){
					output += "\n";
					bin_count <<= 1;
				}
			}
			trace(output);

		}
	}

}